package offer;

import org.w3c.dom.Node;

public class offer_0036 {
    public Node treeToDoublyList(Node root) {
        Node head=new Node();
        if(root==null) return root;
        Node[] flag=new Node[1];
        flag[0]=head;
        inorder(root,flag);
        flag[0].right=head.right;
        head.right.left=flag[0];
        return head.right;
    }
    public void inorder(Node node,Node[] flag){
        if(node==null) return;
        inorder(node.left,flag);
        flag[0].right=node;
        node.left=flag[0];
        flag[0]=node;
        inorder(node.right,flag);
    }
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };
}
